package demo2;

import java.util.Random;

/**
 * @Author liangzai
 * @Description:
 */
public class Test {
    //最小的k个数
    public int[] smallestK(int[] nums, int k) {
        qsort(nums,0,nums.length-1,k);
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = nums[i];
        }
        return ret;
    }

    private void qsort(int[] nums,int l,int r,int k){
        if(l>=r) return ;

        int key = nums[new Random().nextInt(r-l+1)+l];
        int left = l-1; int right = r+1; int i = l;
        while (i < right) {
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]==key) i++;
            else swap(nums,--right,i);
        }

        int a = left-l+1; int b = right-left-1;
        if(a>k) qsort(nums,l,left,k);
        else if(a+b>=k) return ;
        else qsort(nums,right,r,k-a-b);
    }

    private void swap (int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
















